package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-07
 * Description
 */
public class Solution24 {

    /**
     * 方法一， 不确定小数的位数，原理很简单，我们在0 到 x之间取一个中间值，如果中间值的平方大于x
     * 那么，说明最终的结果在0 与  middle之间
     * 否则，最终结果在middle 与 x之间。
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        int left = 0, right = x, res = -1;
        while (left <= right) {
            int mid = left + (right - 1 / 2);
            if ((long) mid * mid <= x) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    /**
     * 方法二，找到一个整数的范围区间，然后在区间内就在阈值范围内符合条件的值
     * @param x
     * @param precise
     * @return
     */
    public static double mySqrt2(int x, double precise) {

        //先确定当前所处的最小整数区间
        int i = 0;
        for ( ; i <= x; i++) {
            if (i * i == x)
                return i;
            if (i * i > x) {
                break;
            }
        }
        double low = i - 1, high = i;
        double middle, squre;
        while (high - low > precise) {
            middle = (low + high) / 2;
            squre = middle * middle;
            if (squre > x) {
                high = middle;
            } else {
                low = middle;
            }
        }
        return (low + high) / 2;
    }
    
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(i + " : " + Math.sqrt(i));
            System.out.println(i + " : " + mySqrt2(i, 1e-8));
        }
    }
}
